﻿#pragma once

#include <cassert>

// 单向链表, 有哨兵位
template <class DataType>
struct chain_node
{
	DataType m_data;
	chain_node* m_next;

	chain_node(const DataType& data = DataType(), chain_node* next = nullptr)
		: m_data(data)
		, m_next(next)
	{

	}

};

template <class DataType>
class chain_iterator
{
public:
	chain_iterator(chain_node<DataType>* node)
		: m_node(node)
	{

	}

	DataType& operator*()
	{
		return m_node->m_data;
	}

	// 前置++
	chain_iterator<DataType> operator++()
	{
		m_node = m_node->m_next;
		return *this;
	}

	bool operator!=(const chain_iterator<DataType>& x)
	{
		return m_node != x.m_node;
	}


private:
	chain_node<DataType>* m_node;
};

template <class DataType>
class chain
{
public:
	typedef chain_iterator<DataType> iterator;

	chain<DataType>()
		: m_sentinel(new chain_node<DataType>)
		, m_size(0)
	{
	
	}

	// 迭代器
	iterator begin()
	{
		return m_sentinel->m_next;
	}

	iterator end()
	{
		//chain_node<DataType>* tail = m_sentinel->m_next;
		//// 找到最后一个节点
		//while (tail != nullptr && tail->m_next != nullptr)
		//{
		//	tail = tail->m_next;
		//}

		return nullptr;
	}

	// 尾插
	void push_back(const DataType& val)
	{
		insert(m_size, val);
	}

	// 插入操作, 链表的下标从0开始
	void insert(int pos, const DataType& val)
	{
		assert(pos >= 0 && pos <= m_size);
		chain_node<DataType>* cur = m_sentinel; // 可视为下标为-1
		// 找到下标为pos-1位置节点
		for (int i = 0; i < pos; ++i)
		{
			cur = cur->m_next;
		}

		chain_node<DataType>* new_node = new chain_node<DataType>(val, cur->m_next);
		cur->m_next = new_node;
		++m_size;
	}

	// 删除操作: 
	// 根据值进行删除, 且仅删除链表中第一个值相同的元素
	// 如果没有该元素返回false
	bool erase(const DataType& val)
	{
		chain_node<DataType>* cur = m_sentinel->m_next;
		chain_node<DataType>* last = m_sentinel;
		while (cur != nullptr)
		{
			if (cur->m_data == val)
			{
				last->m_next = cur->m_next;
				delete cur;
				--m_size;
				return true;
			}

			last = cur;
			cur = cur->m_next;
		}

		return false;
	}

	// 逆置操作
	void reverse()
	{
		chain_node<DataType>* old_cur = m_sentinel->m_next;
		chain_node<DataType>* old_next = nullptr;

		while (old_cur != nullptr)
		{
			old_next = old_cur->m_next;
			if (old_cur == m_sentinel->m_next)
			{
				// 新的尾
				old_cur->m_next = nullptr;
			}
			else
			{
				old_cur->m_next = m_sentinel->m_next;
			}
			m_sentinel->m_next = old_cur;
			old_cur = old_next;
		}

	}

	// 查询操作
	// 根据值进行查找, 仍然若链表中存在多个该元素，仅输出第一个的索引。若不存在该元素，输出 - 1；
	// 返回下标
	int find_by_val(const DataType& val)
	{
		chain_node<DataType>* cur = m_sentinel->m_next;
		for (int i = 0; i < m_size; ++i)
		{
			if (cur->m_data == val)
			{
				return i;
			}
			cur = cur->m_next;
		}

		return -1;
	}

	// 输出操作 : 5，使用 链表迭代器 ，输出当前链表索引与元素的异或和：
	int func_sumxor()
	{
		iterator cur = begin();
		iterator tail = end();

		int cur_index = 0;
		int result = 0;

		while (cur != tail)
		{
			result += (cur_index ^ (*cur));
			++cur;
			++cur_index;
		}

		return result;
	}

	

private:
	chain_node<DataType>* m_sentinel;
	int m_size;

};